package fun.ticsmyc.sort;

import fun.ticsmyc.tools.ArrayTools;
import org.junit.Test;

import java.util.Arrays;

/**
 * 快速排序
 * @author Ticsmyc
 * @date 2020-02-03 18:35
 */
public class QuickSort {

    public void quickSort(int[] arr){
        quickSort(arr,0,arr.length-1);
    }

    public void quickSort(int[] arr,int head , int tail){
        if(head < tail){
            int[] res = divide(arr,head,tail);
            quickSort(arr,head,res[0]);
            quickSort(arr,res[1],tail);
        }
    }

    /**
     * 分隔数组，返回值是小于部分的最后一个数字下标 + 大于部分第一个数字下标
     * @param arr
     * @param head
     * @param tail
     * @return
     */
    public int[] divide(int[] arr,  int head, int tail){
        int left = head-1;
        int right = tail;

        //用tail所在位置的数作为分隔依据
        int partation = arr[tail];
        int cur =head;
        while(cur < right){
            if(arr[cur] < partation){
                ArrayTools.swap(arr,++left,cur++);
            }else if(arr[cur] > partation){
                ArrayTools.swap(arr,--right,cur);
            }else{
                cur++;
            }
        }
        ArrayTools.swap(arr,cur,tail);
        return new int[]{left,right+1};
    }

    @Test
    public void test(){

        //测试次数
        int testTime=5_000_000;
        //数组大小
        int size=10;
        //数组值 -100 ~ +100
        int value=100;
        boolean succeed =true;

        for(int i=0;i<testTime;++i){
            int[] arr1 = ArrayTools.generateRandomArray(size,value);
            int[] arr2 = Arrays.copyOf(arr1,arr1.length);
            int[] arr3 = Arrays.copyOf(arr1,arr1.length);

            quickSort(arr1);
            ArrayTools.rightSortMethod(arr2);
            if(!Arrays.equals(arr1,arr2)){
                succeed=false;
                //打印原数组
                ArrayTools.printArray(arr3);
                break;
            }
        }
        System.out.println( succeed ? "nice" : "Fucking fucked!");
    }
}
